package com.offer;

/** 
 * 面试题3：二维数组的查找 
 * 题目大致为：
 *
 * 一个二维数组，每一行按照从左到右递增，每一列按照从上到下递增，查找数组中是否存在某个数。如数组：
 * 1  2  8    9
 * 2  4  9   12
 * 4  7  10  13
 * 6  8  11  15
 * 思路：
 * 这道题有其特殊性，从右上角或者左下角开始查找的方向是确定的。这句话是说比如是查找7，我们从右上角开始，9大于7，则减少列下标，查找13的话就增加行下表，查找的方向是确定的，这样就容易实现了。
 *  
 */  
public class Item03 {  
    public static void main(String args[]) {  
        // 测试用的例子  
        int A[][] = { { 1, 2, 8, 9 }, { 2, 4, 9, 12 }, { 4, 7, 10, 13 },  
                { 6, 8, 11, 15 } };  
        System.out.println(find(A, 7));  
    }  
      
    /** 
     * 二维数组的查找 
     * @param array 已知的数组 
     * @param number 待查找的数 
     * @return 
     */  
    public static boolean find(int array[][], int number) {  
        boolean flag = false;  
        int rows = array.length;// 行数  
        int columns = array[0].length;// 列数  
        int row = 0;  
        int column = columns - 1;  
        while (row < rows && column >= 0) {  
            // 比较二维数组中的元素与number的关系  
            if (array[row][column] == number) {  
                flag = true;  
                break;// 跳出循环  
            } else if (array[row][column] > number) {  
                // 列变小  
                column--;  
            } else {  
                // 行变大  
                row++;  
            }  
        }  
        return flag;  
    }  
}  